The management of spatial and geometric data rises in various settings, including geographic database systems, astronomy, and very large scale integration (VLSI) design, among others. A spatial database system supports storing, indexing and fast querying of geometric objects. Spatial databases may deal with large collections of relatively simple geometric objects, such as lines, curves, and polygons in space. An important class of objects in spatial databases is rectangles in two or more dimensions.
In the data stream model of computation, an algorithm generally processes data in a single pass and with limited additional workspace. Some advantages of one-pass processing include: maintaining an aggregate in an online manner from an update stream with small space overhead; and even if data is not arriving as a stream, but is stored on locally, a streaming algorithm implicitly yields a small space summary of a large set of objects that can be used to quickly answer a query, along with an approximation error guarantee.